(***) ** Les tours de Hanoï - Grand Oral

Les tours de Hanoï sont un jeu de réflexion proposé par le mathématicien français Édouard Lucas dans le tome 3 de ses Récréations mathématiques, parues à titre posthume en 1892.

Le jeu est constitué de trois piques fixées sur un socle et de  $n$  disques de diamètres différents.  Au départ, les  $n$  disques sont empilés sur la première pique dans l'ordre décroissant de leur diamètre, le plus large étant en dessous.

Ce jeu consiste à déplacer les  $n$  disques de la pique 1 à la pique 3 en un minimum de coups, tout en respectant les règles suivantes :

• on ne peut pas déplacer plus d'un disque à la fois ;
  
• on ne peut placer un disque que sur un autre disque de diamètre supérieur ou sur un emplacement vide.
  

Pour tout entier naturel $n$  non nul, on pose $u_n$  le nombre minimal de déplacements nécessaires pour déplacer une tour de  $n$  étages d'une pique à une autre.

1. Déterminer $u_1$ , $u_2$  et $u_3$ .
2. En observant plus précisément les manipulations nécessaires à la résolution du problème pour $n=3$ , donner une relation liant $u_3$  et $u_2$ .
3. a. Pour tout entier naturel $n$ , exprimer $u_{n+1}$  en fonction de $u_n$ .
    b. Démontrer par récurrence que, pour tout entier naturel  $n$ , $u_n=2^n-1$ .
4. Ci-dessous un extrait du texte original :

En supposant qu'il faut une seconde pour déplacer un disque, estimer le nombre d'années qui devront s'écouler avant que les brahmes ne tombent.